package q17_letterCombinations;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    public static void main(String[] args) {
        System.out.println(letterCombinations("2345"));
    }

    public static List<String> letterCombinations(String digits) {
        List<String> list = new ArrayList<>();
        if ("".equals(digits)) {
            return list;
        }
        // 递归？
        Map<String, String> map = new HashMap<>();
        map.put("2","abc");
        map.put("3","def");
        map.put("4","ghi");
        map.put("5","jkl");
        map.put("6","mno");
        map.put("7","pqrs");
        map.put("8","tuv");
        map.put("9","wxyz");
        return methodComb(list,map,digits);
    }

    private static List<String> methodComb(List<String> list, Map<String, String> map, String digits) {
        List<String> newList = new ArrayList<>();
        if((digits.length() == 1) && list.size() == 0){
            for (int i = 0; i < map.get(digits).length(); i++) {
                newList.add(String.valueOf(map.get(digits).charAt(i)));
            }
            return newList;
        }else if (digits.length() == 1) {
            for (String s : list) {
                for (int i = 0; i < map.get(digits).length(); i++) {
                    newList.add(s + map.get(digits).charAt(i));
                }
            }
            return newList;
        }else if (list.size() == 0) {
            for (int i = 0; i < map.get(digits.substring(0,1)).length(); i++) {
                newList.add(String.valueOf(map.get(digits.substring(0,1)).charAt(i)));

            }
            return methodComb(newList,map,digits.substring(1));
        }

        for (String s : list) {
            for (int i = 0; i < map.get(digits.substring(0,1)).length(); i++) {
                newList.add(s + map.get(digits.substring(0,1)).charAt(i));
            }
        }

        return methodComb(newList,map,digits.substring(1));

    }
}
